public class Solution837 {
    public double new21Game(int n, int k, int maxPts) {
        if (k==0){
            return 1;
        }
        double[] f=new double[k+maxPts];
        for (int i=1;i<=maxPts;i++){
            f[i]=1.0/maxPts;
        }
        double pre=0;
        for (int i=1;i<=k-1+maxPts;i++){
            f[i]+=pre/maxPts;
            if (i<k) {
                pre += f[i];
            }
            if (i>maxPts){
                pre-=f[i-maxPts];
            }
        }
        double a=0;
        for (int i=k;i<=k-1+maxPts;i++){
            a+=f[i];
        }
        double b=0;
        for (int i=k;i<=Math.min(n,k-1+maxPts);i++){
            b+=f[i];
        }
        return b/a;
    }

    public static void main(String[] args) {
        System.out.println(new Solution837().new21Game(21,17,10));
    }
}
